import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution().nextGreaterElements(new int[]{1, 2, 1})));
        System.out.println(Arrays.toString(new Solution().nextGreaterElements(new int[]{1, 2, 3, 4, 3})));
    }
}

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] ans = new int[nums.length];
        Deque<Integer> stack = new ArrayDeque<>();

//        //第一次循环
//        for (int i = 0; i < nums.length; i++) {
//            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
//                int top = stack.pop();
//                ans[top] = nums[i];
//            }
//            stack.push(i);
//        }
//        //第二次循环
//        for (int i = 0; !stack.isEmpty() && i < stack.peek(); i++) {
//            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
//                int top = stack.pop();
//                ans[top] = nums[i];
//            }
//        }
        while (!stack.isEmpty()) {
            ans[stack.pop()] = -1;
        }

        //或者两次循环放一起
        Arrays.fill(ans, -1);    //先填充数组为-1
        for (int i = 0; i < nums.length * 2 - 1; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % nums.length]) {
                int top = stack.pop();
                ans[top] = nums[i % nums.length];
            }
            stack.push(i % nums.length);
        }

        return ans;
    }
}